import random
import Core.utils as utils


# 算法主体
def dbscan(Data, Eps, MinPts):
    # 拿到处理好的Dataset中的"点集"
    num = len(Data)
    # 设置所有点为未访问的点
    unvisited = [i for i in range(num)]
    # 设置已访问点的列表
    visited = []
    # C为输出的簇结果, 初始化为全-1(默认认为全是噪声点)
    C = [-1 for i in range(num)]
    # 使用k标记不同object, k=-1代表噪声点
    k = -1

    # 开始循环(结束条件为所有点都被访问过了)
    while len(unvisited) > 0:
        # 随机选出一个未访问的点p
        p = random.choice(unvisited)
        unvisited.remove(p)
        visited.append(p)
        # 设N为p的epsilon邻域中objects的集合
        N = []
        for i in range(num):
            if utils.get_distance(Data[i], Data[p]) <= Eps:
                N.append(i)

        # 接下来判断如果p点的epsilon邻域中的objects对象数大于指定阈值, 说明p是一个核心对象
        if len(N) >= MinPts:
            # 某个簇对应不同的值...
            k = k+1
            C[p] = k
            # 对于p的epsilon邻域中的每一个object
            for pi in N:
                if pi in unvisited:
                    unvisited.remove(pi)
                    visited.append(pi)
                    # 判断每个pi的所属类型
                    # 如果是核心再去找该pi的邻域内的objects, 再对这些objects迭代讨论...
                    # 设M是位于pi的邻域内的objects的集合
                    M = []
                    for j in range(num):
                        if utils.get_distance(Data[j], Data[pi]) <= Eps:
                            M.append(j)
                    if len(M) >= MinPts:
                        # 将该核心object的邻域内objects放入N循环迭代讨论
                        for t in M:
                            if t not in N:
                                N.append(t)
                # 若pi还不属于任何簇, C[pi] == -1说明C中pi值没有改动(此object为边界点)
                if C[pi] == -1:
                    C[pi] = k
        # 没有到达最低阈值 --> 噪声点
        else:
            C[p] = -1
    # 算法结束
    return C